#define _CRT_SECURE_NO_WARNINGS 1

#include <vector>
using namespace std;

class Solution {
public:
    void mergesort(vector<int>& nums, int begin, int end, int* tmp)
    {
        if (begin == end) return;
        int mid = (begin + end) / 2;
        mergesort(nums, begin, mid, tmp);
        mergesort(nums, mid + 1, end, tmp);
        int n = end - begin + 1;
        int left = begin;
        int right = mid + 1;
        int i = begin;
        while (left < mid + 1 && right < end + 1)
        {
            if (nums[left] <= nums[right]) tmp[i++] = nums[left++];
            else tmp[i++] = nums[right++];
        }
        while (i < end + 1)
        {
            if (left < mid + 1) tmp[i++] = nums[left++];
            else tmp[i++] = nums[right++];
        }
        i = begin;
        for (int j = begin; j < end + 1; ++j)
        {
            nums[j] = tmp[i++];
        }
    }
    vector<int> sortArray(vector<int>& nums) {
        int* tmp = new int[nums.size()];
        mergesort(nums, 0, nums.size() - 1, tmp);
        delete[] tmp;
        return nums;
    }
};